【题解】 [Violet]天使玩偶/SJY摆棋子 K-D Tree luoguP4169/bzoj2648 | Qiuly's blog!

【题解】 [Violet]天使玩偶/SJY摆棋子 K-D Tree luoguP4169/bzoj2648

Posted on | Edited on | In | Comments:

$KDT$ 大法好！

直接建 $KDT$ 维护一下所有的可能存在玩偶的结点，该插入的时候插入，查询的时候只需要沿着 $KDT$ 往下走，然后随时对 $ans$ 取 $min$ 即可。

注意这题有插入，这意味着 $KDT$ 到后面或许会不平衡，这个时候我们就需要用替罪羊树的思想——拍扁重建即可。注意这里判断是否平衡的 $check$ 函数需要放在 $insert$ 的最后，也就是还要在 $pushup$ 以后再 $check$ 即可。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e6+7;
const int inf=1e9+9;
#define alph (0.75)

template <typename _Tp> inline void IN(_Tp&x) {
    char ch=0;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int root,ans,WD,trh[N],top,cnt;
struct point{int x[2];}p[N];
struct node {
    int mi[2],mx[2],l,r,sz;
    point tp;
}tr[N];
int operator < (point a,point b) {return a.x[WD]<b.x[WD];}
inline int new_node() {
    if(top) return trh[top--];
    else return ++cnt;
}
inline void pushup(int x) {
    int l=tr[x].l,r=tr[x].r;
    tr[x].sz=tr[l].sz+tr[r].sz+1;
    for(int i=0;i<=1;++i) {
        tr[x].mi[i]=tr[x].mx[i]=tr[x].tp.x[i];
        if(l) {
            tr[x].mi[i]=min(tr[x].mi[i],tr[l].mi[i]);
            tr[x].mx[i]=max(tr[x].mx[i],tr[l].mx[i]);
        } 
        if(r) {
            tr[x].mi[i]=min(tr[x].mi[i],tr[r].mi[i]);
            tr[x].mx[i]=max(tr[x].mx[i],tr[r].mx[i]);
        }
    }
}
int build(int l,int r,int wd) {
    if(l>r) return 0;
    int x=new_node(),mid=(l+r)>>1;
    WD=wd,nth_element(p+l,p+mid,p+r+1),tr[x].tp=p[mid];
    tr[x].l=build(l,mid-1,wd^1);
    tr[x].r=build(mid+1,r,wd^1);
    return pushup(x),x;
}
void pia(int x,int num) {
    if(tr[x].l) pia(tr[x].l,num);
    p[num+tr[tr[x].l].sz+1]=tr[x].tp,trh[++top]=x;
    if(tr[x].r) pia(tr[x].r,num+tr[tr[x].l].sz+1);
}
void check(int&x,int wd) {
    if(alph*tr[x].sz<tr[tr[x].l].sz||alph*tr[x].sz<tr[tr[x].r].sz)
        pia(x,0),x=build(1,tr[x].sz,wd);
}
void Insert(point tmp,int&x,int wd) {
    if(!x) {
        x=new_node();
        tr[x].tp=tmp,tr[x].l=tr[x].r=0;
        pushup(x);return;
    }
    if(tr[x].tp.x[wd]<tmp.x[wd]) Insert(tmp,tr[x].r,wd^1);
    else Insert(tmp,tr[x].l,wd^1);
    pushup(x);check(x,wd);
}
int getdist(point tmp,int x) {
    int res=0;
    for(int i=0;i<=1;++i)   
        res+=max(0,tmp.x[i]-tr[x].mx[i])+max(0,tr[x].mi[i]-tmp.x[i]);
    return res;
}
int dist(point a,point b) {
    return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);
}
void query(point tmp,int x) {
    ans=min(ans,dist(tmp,tr[x].tp));
    int disl=inf,disr=inf;
    if(tr[x].l) disl=getdist(tmp,tr[x].l);
    if(tr[x].r) disr=getdist(tmp,tr[x].r);
    if(disl<disr) {
        if(disl<ans) query(tmp,tr[x].l);
        if(disr<ans) query(tmp,tr[x].r);
    } else {
        if(disr<ans) query(tmp,tr[x].r);
        if(disl<ans) query(tmp,tr[x].l);
    }
}

int main() {
    int n,m,op;
    IN(n),IN(m);
    for(int i=1;i<=n;++i)
        IN(p[i].x[0]),IN(p[i].x[1]);
    root=build(1,n,0);
    for(int i=1;i<=m;++i) {
        point tmp;
        IN(op),IN(tmp.x[0]),IN(tmp.x[1]);
        if(op==1) Insert(tmp,root,0);
        else {
            ans=inf;query(tmp,root);
            printf("%d\n",ans);
        }
    }return 0;
}

本文标题:【题解】 [Violet]天使玩偶/SJY摆棋子 K-D Tree luoguP4169/bzoj2648

文章作者:Qiuly

发布时间:2019年03月21日 - 00:00

最后更新:2019年03月29日 - 14:10

原始链接:http://qiulyblog.github.io/2019/03/21/[题解]luoguP4169/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。